package com.computer.fundamentals.algorithm;


import com.computer.fundamentals.datastructure.node.BinaryTreeNode;
import com.computer.util.UniversalMethod;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 经典问题-序列化与反序列化二叉树
 */
public class SerializeBinaryTree {

    /**
     * 序列化
     */
    public static String serialize(BinaryTreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        StringBuilder res = new StringBuilder();
        res.append('[');
        while (!queue.isEmpty()) {
            BinaryTreeNode node = queue.poll();
            if (node == null) {
                res.append("N,");
            }else {
                res.append(node.val).append(",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        res.deleteCharAt(res.length() - 1);
        res.append(']');
        return res.toString();
    }

    /**
     * 反序列化
     */
    public static BinaryTreeNode deserialize(String data) {
        if (data == null) {
            return null;
        }
        String[] nodes = data.substring(1, data.length()-1).split(",");
        BinaryTreeNode root = new BinaryTreeNode(Integer.parseInt(nodes[0]));
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while (i < nodes.length) {
            BinaryTreeNode node = queue.poll();
            assert node != null;
            if (!nodes[i].equals("N")) {
                node.left = new BinaryTreeNode(Integer.parseInt(nodes[i]));
                queue.offer(node.left);
            }
            i++;
            if (!nodes[i].equals("N")) {
                node.right = new BinaryTreeNode(Integer.parseInt(nodes[i]));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }

    /**
     * 测试, 详细测试前往 https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
     */
    public static void main(String[] args) {

        System.out.println("------------测试------------");
        String data = serialize(UniversalMethod.createBinaryTree().root);
        System.out.println(data);
        System.out.println(deserialize(data));

    }
}
